package codeTop;

import java.util.Map;

public class q42 {
    //动态规划
    public int trap1(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int leftMax = 0;
        for (int i = 0; i < n; i++) {
            leftMax = Math.max(leftMax,height[i]);
            left[i] = leftMax;
        }
        int[] right = new int[n];
        int rightMax = 0;
        for (int i = n-1; i >=0 ; i--) {
            rightMax = Math.max(rightMax,height[i]);
            right[i] = rightMax;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.min(left[i],right[i])-height[i];
        }
        return sum;
    }
    //双指针
    public int trap(int[] height) {
        int n = height.length;
        int l = 0;
        int r = n-1;
        int sum = 0;
        int maxLeft = height[l];
        int maxRight = height[r];
        while (l < r) {
            if (maxLeft <= maxRight) {
                sum+=maxLeft-height[l];
                l++;
                maxLeft = Math.max(maxLeft,height[l]);
            }else {
                sum+=maxRight-height[r];
                r--;
                maxRight = Math.max(maxRight,height[r]);
            }
        }
        return sum;
    }
}
